package com.example.algorithm.leetcode;

import java.util.Arrays;

/**
 * @author yuzhenxin
 * @date 2023-03-04 1:00
 * @description Leetcode-31：下一个排列
 */
public class NextPermutation {

    public static void main(String[] args) {
        int[] nums = {5, 4, 7, 5, 3, 2};
        new NextPermutation().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void nextPermutation(int[] nums) {
        int a = -1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i > 0 && nums[i - 1] < nums[i]) {
                a = i - 1;
                break;
            }
        }
        if (a == -1) {
            reverse(nums, 0);
            return;
        }
        int b = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] > nums[a]) {
                b = i;
                break;
            }
        }
        swap(nums, a, b);
        reverse(nums, a + 1);
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

}
